1728E - Red-Black Pepper - CodeForces Solution

#include <iostream>
#include <bits/stdc++.h>

// policy based datastructure
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
// typedef tree<int,null_type,less<int>,rb_tree_tag,
// tree_order_statistics_node_update> indexed_set;

#define ll long long
#define en '\n'
#define ff first
#define ss second
#define pb push_back
#define MP make_pair
#define mod 1000000007
#define mod2 998244353
#define fast                      \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
using namespace std;

typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef priority_queue<ll> pqi;
typedef priority_queue<ll, vi, greater<ll>> minpqi;
typedef pair<ll, ll> pii;
#define debarr(a, n)            \
    cout << #a << " : ";        \
    for (int i = 0; i < n; i++) \
        cerr << a[i] << " ";    \
    cerr << endl;
#define debmat(mat, row, col)         \
    cout << #mat << " :\n";           \
    for (int i = 0; i < row; i++)     \
    {                                 \
        for (int j = 0; j < col; j++) \
            cerr << mat[i][j] << " "; \
        cerr << endl;                 \
    }
#define pr(...) dbs(#__VA_ARGS__, __VA_ARGS__)
template <class S, class T>
ostream &operator<<(ostream &os, const pair<S, T> &p)
{
    return os << "(" << p.first << ", " << p.second << ")";
}
template <class T>
ostream &operator<<(ostream &os, const vector<T> &p)
{
    os << "[ ";
    for (auto &it : p)
        os << it << " ";
    return os << "]";
}
template <class T>
ostream &operator<<(ostream &os, const unordered_set<T> &p)
{
    os << "[ ";
    for (auto &it : p)
        os << it << " ";
    return os << "]";
}
template <class S, class T>
ostream &operator<<(ostream &os, const unordered_map<S, T> &p)
{
    os << "[ ";
    for (auto &it : p)
        os << it << " ";
    return os << "]";
}
template <class T>
ostream &operator<<(ostream &os, const set<T> &p)
{
    os << "[ ";
    for (auto &it : p)
        os << it << " ";
    return os << "]";
}
template <class T>
ostream &operator<<(ostream &os, const multiset<T> &p)
{
    os << "[ ";
    for (auto &it : p)
        os << it << " ";
    return os << "]";
}
template <class S, class T>
ostream &operator<<(ostream &os, const map<S, T> &p)
{
    os << "[ ";
    for (auto &it : p)
        os << it << " ";
    return os << "]";
}
template <class T>
void dbs(string str, T t) { cerr << str << " : " << t << "\n"; }
template <class T, class... S>
void dbs(string str, T t, S... s)
{
    int idx = str.find(',');
    cerr << str.substr(0, idx) << " : " << t << ",";
    dbs(str.substr(idx + 1), s...);
}
template <class T>
void prc(T a, T b)
{
    cerr << "[";
    for (T i = a; i != b; ++i)
    {
        if (i != a)
            cerr << ", ";
        cerr << *i;
    }
    cerr << "]\n";
}
#define all(x) x.begin(), x.end()
#define present(c, key) (find(all(c), key) != c.end())
#define tr(c, it) for (auto it : c)
#define fr(i, s, e) for (ll i = s; i < e; i++)
#define revfr(i, s, e) for (ll i = s - 1; i >= e; i--)
#define getv(v, n)             \
    for (ll i = 0; i < n; i++) \
        cin >> v[i];

template <typename T>
ostream &operator<<(ostream &os, vector<T> &v)
{

    for (auto element : v)
    {
        os << element << ' ';
    }
    return os;
}
inline void add(ll &a, ll b)
{
    a += b;
    if (a >= mod)
        a -= mod;
}

inline void sub(ll &a, ll b)
{
    a -= b;
    if (a < 0)
        a += mod;
}

inline ll mul(ll a, ll b, ll p = mod)
{
    return (ll)((long long)a * b % p);
}

inline ll power(ll a, long long b, ll p = mod)
{
    ll res = 1;
    while (b > 0)
    {
        if (b & 1)
        {
            res = mul(res, a, p);
        }
        a = mul(a, a, p);
        b >>= 1;
    }
    return res;
}
inline ll binpow(ll a, long long b)
{
    ll res = 1;
    while (b > 0)
    {
        if (b & 1)
        {
            res = res * a;
        }
        a = a * a;
        b >>= 1;
    }
    return res;
}
inline ll inv(ll a, ll p = mod)
{
    a %= p;
    if (a < 0)
        a += p;
    ll b = p, u = 0, v = 1;
    while (a)
    {
        ll t = b / a;
        b -= t * a;
        swap(a, b);
        u -= t * v;
        swap(u, v);
    }
    if (u < 0)
        u += p;
    return u;
}
// inline ll lsb(ll x)
// {
//     return x&(~(x-1));
// }
// ll modexp2(ll a, ll b, ll c, ll p) // calculate (a^(b^c))%prime
// {
//     // By Fermat's Little Theorem (a^(p-1))%p = 1 if p is prime
//     ll x = power(b,c,p-1);  // so we first find remainder when b^c is divided by p-1
//     return (power(a,x,p));  // then just do (a^remainder)%p

// }
ll gcd(ll a, ll b)
{
    if (a == 0 or b == 0)
        return a ^ b;
    return gcd(b, a % b);
}
ll lcm(ll a, ll b)
{
    return a * (b / gcd(a, b));
}
void fread()
{
    // #ifdef ONLINE_JUDGE
    freopen("./input.txt", "r", stdin);
    freopen("./output.txt", "w", stdout);
    // #endif
}

void solve()
{
    ll n, q;
    cin >> n;
    vector<pii> v;
    fr(i, 0, n)
    {
        ll a, b;
        cin >> a >> b;
        v.pb({a, b});
    }
    sort(all(v), [&](pii a, pii b)
         { return (a.ff - a.ss) > (b.ff - b.ss); });
    vi pre(n + 1, 0), suff(n + 1, 0);
    fr(i, 0, n) pre[i + 1] = (pre[i] + v[i].ff);
    revfr(i, n, 0) suff[i] = (suff[i + 1] + v[i].ss);
    ll pos = 0, mAx = suff[0] + pre[0];
    fr(i, 0, n + 1)
    {
        if (mAx < (pre[i] + suff[i]))
        {
            pos = i;
            mAx = pre[i] + suff[i];
        }
    }
    cin >> q;
    map<pii, ll> mp;
    while (q--)
    {
        ll x, y;
        cin >> x >> y;
        ll gc = gcd(x, y);
        if (n % gc)
        {
            cout << "-1\n";
            continue;
        }
        if (mp.find({x, y}) != mp.end())
            cout << mp[{x, y}] << en;
        else
        {
            ll ans = 0;
            ll flag = 0;
            if (x < y)
            {
                swap(x, y);
                flag = 1;
            }
            ll n1 = n / gc;
            x /= gc;
            y /= gc;
            ll a = -1, b = -1;
            fr(i, 0, y + 1)
            {
                if (n1 < (i * x))
                    break;
                if (n1 % y == ((i * x) % y))
                {
                    a = i;
                    b = (n1 - (i * x)) / y;
                    if (flag)
                    {
                        swap(a, b);
                        swap(x, y);
                    }
                    break;
                }
            }
            x *= gc;
            y *= gc;
            if (a == -1)
            {
                mp[{x, y}] = -1;
                cout << "-1\n";
                continue;
            }
            // all solution of ax+by=c is given by (x0+k*b/g,y0-k*a/g); for all integers k
            ll move = (x * y) / gc;
            ll st = (a * x);
            st += ((pos - st) / move) * move;
            while (st < 0)
                st += move;
            while (st > n)
                st -= move;
            ans = (pre[st] + suff[st]);
            if (st < pos)
                st += move;
            while (st > n)
                st -= move;
            ans = max(ans, pre[st] + suff[st]);
            if (st > pos)
                st -= move;
            while (st < 0)
                st += move;
            ans = max(ans, pre[st] + suff[st]);
            mp[{x, y}] = ans;
            cout << ans << en;
        }
    }
}
using namespace std;

int main()
{
    fast
    // fread();
    ll _t = 1;
    // cin >> _t;
    fr(i, 1, _t + 1)
    {
        // cout<<"Case #"<<i<<": ";
        // cerr<<"i="<<i<<en;
        solve();
    }
    return 0;
}